八皇后
# 八皇后
[TOC]
# 一、算法核心思想
- 递归回溯
解决八皇后问题，可以分为两个层面：
1.找出第一种正确摆放方式，也就是深度优先遍历。
2.找出全部的正确摆放方式，也就是广度优先遍历。
# 二、算法实现（DFS）
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta http-equiv="X-UA-Compatible" content="ie=edge">
<title>八皇后</title>
<style>
body {
display: flex;
min-height: 100vh;
}
#chess {
width: 248px;
height: 248px;
margin: auto;
border-top: 1px solid #000;
border-left: 1px solid #000;
}
.grid {
width: 30px;
height: 30px;
border-right: 1px solid #000;
border-bottom: 1px solid #000;
display: inline-block;
/* 指定行内垂直对齐方式 */
vertical-align: top;
}
</style>
</head>
<body>
<div id="chess"></div>
<script>
// 棋盘制作
// 结构：生成8×8的二维数组
let data = Array(8).fill(0);
for (let i = 0; i < data.length; i++) {
data[i] = Array(8).fill(0);
}
// 检查新皇后摆放的位置是否符合规则
// 只需要考虑前几行摆放的皇后，因为后面没摆放
function check(x, y) {
for (let i = 0; i < x; i++) {
// 检查纵向
if (data[i][y] == 1) {
return false;
}
// 检查斜向1
// i+j = x+y
// 要避免数组越界
if ((x + y - i >= 0 && x + y - i < 8) && data[i][x + y - i] == 1) {
return false;
}
// 检查斜向2
// |i-j| = |x-y|
if ((i + y - x >= 0 && i + y - x < 8) && data[i][i + y - x] == 1) {
return false;
}
}
return true;
}
// 找八皇后
// 递归：一行一行的去放皇后
// 回溯：当前行无法放皇后，则回溯到上一行，将上一行皇后往右方向放置
function queens(x) {
// 说明已经全部放好了
if (x == 8) return true;
// 遍历当前行，逐一验证
for (let j = 0; j < 8; j++) {
// 避免回溯时出现脏数据
for (let j = 0; j < 8; j++) {
data[x][j] = 0;
}
if (check(x, j)) {
data[x][j] = 1;
// 遍历下一行,如果下一行返回true,则无须回溯至此行
// 否则继续向右遍历
if(queens(x+1)) return true;
}
}
}
queens(0);
// 样式
let chess = document.getElementById("chess");
for (let i = 0; i < 8; i++) {
for (let j = 0; j < 8; j++) {
let grid = document.createElement("div");
grid.className = "grid";
if(data[i][j]==1){
grid.style.background = "#000";
}
chess.appendChild(grid);
}
}
</script>
</body>
</html>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112